package problem173_Binary_Search_Tree_Iterator;

import java.util.Stack;

import problem105_Construct_Binary_Tree_from_Preorder_and_Inorder_Traversal.MySolution.TreeNode;

public class BSTIterator {
	Stack<TreeNode> stack=new Stack<>();
	
	public BSTIterator(TreeNode root) {
        pushLeft(root);
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    /** @return the next smallest number */
    public int next() {
        if(!hasNext())
        	return -1;
        TreeNode node=stack.pop();
        pushLeft(node.right);
        return node.val;
    }
    
    private void pushLeft(TreeNode root){
    	while(root!=null){
        	stack.push(root);
        	root=root.left;
        }
    }
}
